An important feature associated with cryptography is the provision of a trusted authority, where a trusted authority is responsible for issuing private and public keys to appropriate individuals/entities. However, as a private key, is by its nature, private to a specific individual/entity it is essential that a user can trust that the trusted authority will not disclose or otherwise use the user's private key in an inappropriate manner. However, it can be difficult for a user to build a strong trust relationship with a single trusted authority.
One solution to this problem has involved the use of a plurality of trusted authorities to generate individual parts of a private key, where no one trusted authority has access to the complete private key. In particular, one solution involves the use of a shared secret in which a group of trusted authorities use the shared secret to generate their portion of the private key. However, this solution requires the use of a trusted secret distributor.
Another solution involves each trusted authority providing a portion of a private key based upon the identity of the user where the identity of the user is the same for each trusted authority. However, in many applications a user may have different identities when dealing with the different trusted authorities.
It is desirable to improve this situation.
Embodiments of the present invention to be described hereinafter make use of cryptographic techniques using bilinear mappings. Accordingly, a brief description will now be given of certain such prior art techniques.
In the present specification, G1 and G2 denote two algebraic groups of prime order q in which the discrete logarithm problem is believed to be hard and for which there exists a computable bilinear map p, for example, a Tate pairing t or Weil pairing ê. Thus, for the Weil pairing:ê: G1×G1→G2where G2 is a subgroup of a multiplicative group of a finite field. The Tate pairing can be similarly expressed though it is possible for it to be of asymmetric form:t: G1×G0→G2where G0 is a further algebraic group the elements of which are not restricted to being of order q. Generally, the elements of the groups G0 and G1 are points on an elliptic curve though this is not necessarily the case. For convenience, the examples given below assume the elements of G0 and G1 to be points on an elliptic curve and use a symmetric bilinear map (p: G1×G1→G2); however, these particularities, are not to be taken as limitations on the scope of the present invention.
As is well known to persons skilled in the art, for cryptographic purposes, a modified form of the Weil pairing is used that ensure p (P,P)≠1 where P ∈ G1; however, for convenience, the pairing is referred to below simply by its usual name without labeling it as modified. Further background regarding Weil and Tate pairings and their cryptographic uses can be found in the following references:                G. Frey, M. Müller, and H. Rück. The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems. IEEE Transactions on Information Theory, 45(5):1717-1719, 1999.        D. Boneh and M. Franklin. Identity based encryption from the Weil pairing. In Advances in Cryptology—CRYPTO 2001, LNCS 2139, pp. 213-229, Springer-Verlag, 2001.        
For convenience, the examples given below assume the use of a symmetric bilinear map (p. G1×G1→G2) with the elements of G1 being points on an elliptic curve; however, these particularities, are not to be taken as limitations on the scope of the present invention.
As the mapping between G1 and G2 is bilinear exponents/multipliers can be moved around. For example if a, b, c ∈ Fq and P, Q ∈ G1 then
                                          t            ⁡                          (                              aP                ,                bQ                            )                                c                =                ⁢                                            t              ⁡                              (                                  aP                  ,                  cQ                                )                                      b                    =                                                    t                ⁡                                  (                                      bP                    ,                    cQ                                    )                                            a                        =                                                            t                  ⁡                                      (                                          bP                      ,                      aQ                                        )                                                  c                            =                                                                    t                    ⁡                                          (                                              cP                        ,                        aQ                                            )                                                        b                                =                                                      t                    ⁡                                          (                                              cP                        ,                        bQ                                            )                                                        a                                                                                            =                ⁢                                            t              ⁡                              (                                  abP                  ,                  Q                                )                                      c                    =                                    t              ⁡                              (                                  abP                  ,                  cQ                                )                                      =                                                            t                  ⁡                                      (                                          P                      ,                      abQ                                        )                                                  c                            =                              t                ⁡                                  (                                      cP                    ,                    abQ                                    )                                                                                            =                ⁢        …                                =                ⁢                              t            ⁡                          (                              abcP                ,                Q                            )                                =                                    t              ⁡                              (                                  P                  ,                  abcQ                                )                                      =                                          t                ⁡                                  (                                      P                    ,                    Q                                    )                                            abc                                          
Additionally, the following cryptographic hash functions are defined:H1: {0,1}*→G1H2: {0,1}*→FqH3: G2→{0,1}*
A normal public/private key pair can be defined for a trusted authority:                the private key is s where s ∈ Fq         the public key is (P, R) where P ∈ G1 and R ∈ G1, with R=sP        
Additionally, an identifier based public key/private key pair can be defined for a party with the cooperation of the trusted authority. As is well known to persons skilled in the art, in “identifier-based” cryptographic methods a public, cryptographically unconstrained, string is used in conjunction with public data of a trusted authority to carry out tasks such as data encryption or signing. The complementary tasks, such as decryption and signature verification, require the involvement of the trusted authority to carry out computation based on the public string and its own private data. Frequently, the string serves to “identify” the intended message recipient and this has given rise to the use of the label “identifier-based” or “identity-based” generally for these cryptographic methods. However, depending on the application to which such a cryptographic method is put, the string may serve a different purpose to that of identifying the intended recipient and, indeed, may be an arbitrary string having no other purpose than to form the basis of the cryptographic processes. Accordingly, the use of the term “identifier-based” herein in relation to cryptographic methods and systems is to be understood simply as implying that the methods and systems are based on the use of a cryptographically unconstrained string whether or not the string serves to identify the intended recipient. Furthermore, as used herein the term “string” is simply intended to imply an ordered series of bits whether derived from a character string, a serialized image bit map, a digitized sound signal, or any other data source.
In the present case, the identifier-based public/private key pair defined for the party has a public key QID and private key SID where QID, SID ∈ G1. The trusted authority's normal public/private key pair (P,R/s) is linked with the identifier-based public/private key bySID=sQID and QID=H1 (ID)where ID is the identifier string for the party.
Some typical uses for the above described key pairs will now be given with reference to FIG. 1 of the accompanying drawings that depicts a trusted authority 10 with a public key (P, sP) and a private key s. A party A serves as a general third party whilst for the identifier-based cryptographic tasks (IBC) described, a party B has an IBC public key QID and an IBC private key SID.
Standard Signatures (see dashed box 2): The holder of the private key s (that is, the trusted authority 1 or anyone to whom the latter has disclosed s) can use s to sign a bit string; more particularly, where m denotes a message to be signed, the holder of s computes:V=sH1(m).
Verification by party A involves this party checking that the following equation is satisfied:t(P, V)=t(R, H1(m))This is based upon the mapping between G1 and G2 being bilinear exponents/multipliers, as described above. That is to say,
                              t          ⁡                      (                          P              ,              V                        )                          =                ⁢                  t          ⁡                      (                          P              ,                                                sH                  1                                ⁡                                  (                  m                  )                                                      )                                                  =                ⁢                              t            ⁡                          (                              P                ,                                                      H                    1                                    ⁡                                      (                    m                    )                                                              )                                s                                        =                ⁢                  t          ⁡                      (                          sP              ,                                                H                  1                                ⁡                                  (                  m                  )                                                      )                                                  =                ⁢                  t          ⁡                      (                          R              ,                                                H                  1                                ⁡                                  (                  m                  )                                                      )                              
Identifier-Based Encryotion (see dashed box 3):—Identifier based encryption allows the holder of the private key SID of an identifier based key pair (in this case, party B) to decrypt a message sent to them encrypted (by party A) using B's public key QID.
More particularly, party A, in order to encrypt a message m, first computes:U=rPwhere r is a random element of Fq. Next, party A computes:V=m ⊕ H3(t(R, rQID))
Party A now has the ciphertext elements U and V which it sends to party B.
Decryption of the message by party B is performed by computing:
                              V          ⊕                      H3            ⁢                                                  ⁢                          (                              t                ⁡                                  (                                      U                    ,                                          S                      ID                                                        )                                            )                                      =                ⁢                  V          ⊕                                    H              3                        ⁡                          (                              t                ⁡                                  (                                      rP                    ,                                          sQ                      ID                                                        )                                            )                                                              =                ⁢                  V          ⊕                                    H              3                        ⁡                          (                                                t                  ⁡                                      (                                          P                      ,                                              Q                        ID                                                              )                                                  rs                            )                                                              =                ⁢                  V          ⊕                                    H              3                        ⁡                          (                              t                ⁡                                  (                                      sP                    ,                                          rQ                      ID                                                        )                                            )                                                              =                ⁢                  V          ⊕                                    H              3                        ⁡                          (                              t                ⁡                                  (                                      R                    ,                                          rQ                      ID                                                        )                                            )                                                              =                ⁢        m            
Identifier-Based Signatures (see dashed box 4):—Identifier based signatures using Tate pairing can be implemented. For example:
Party B first computes:r=t(SID, P)kwhere k is a random element of Fq.
Party B then apply the hash function H2 to m∥r (concatenation of m and r) to obtain:h=H2(m∥r).
Thereafter party B computesU=(k−h)SIDthus generating the output U and h as the signature on the message m.
Verification of the signature by party A can be established by computing:r′=t(U, P)·t(QID, R)hwhere the signature can only be accepted if h=H2 (m∥r′).